package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-06-17 16:42
 */
public class 题库_0122_买卖股票的最佳时机II {

  static
  class Solution {

    public int maxProfit(int[] prices) {
      if (prices == null || prices.length == 0) {
        return 0;
      }
      // 持有股票时，手里的收益
      int hold = -prices[0];
      // 不持有股票时，手里的收益
      int nonHold = 0;
      for (int i = 1; i < prices.length; ++i) {
        int todayHold = Math.max(hold, nonHold - prices[i]);
        int todayNonHold = Math.max(nonHold, hold + prices[i]);
        hold = todayHold;
        nonHold = todayNonHold;
      }
      return nonHold;
    }

    public int maxProfit1(int[] prices) {
      if (prices == null || prices.length == 0) {
        return 0;
      }
      // 持有股票时，手里的收益
      int[] hold = new int[prices.length];
      hold[0] = -prices[0];

      // 不持有股票时，手里的收益
      int[] nonHold = new int[prices.length];
      nonHold[0] = 0;

      for (int i = 1; i < prices.length; ++i) {
        // 今天持有：昨天已经持有了，今天啥也不干；昨天没持有 + 今天买入
        hold[i] = Math.max(hold[i - 1], nonHold[i - 1] - prices[i]);
        // 今天不持有，昨天就没有持有，今天啥也不干；昨天持有 + 今天卖出
        nonHold[i] = Math.max(nonHold[i - 1], hold[i - 1] + prices[i]);
      }

      return nonHold[prices.length - 1];
    }
  }

}
